export class Dijkstra {
  // 顶点列表
  private vertexList: string[] = [];
  // 各顶点距离 (无向图)
  private vertexMap: Map<string, number> = new Map();

  private flagVertex: { [vertexId: string]: boolean } = {};
  private preVertex: { [vertexId: string]: string } = {};
  private initVertexMap: Map<string, number> = new Map(); // 初始图

  private MAX_LEN = 20000; // 默认最大距离,实际值不会大于该值
  constructor(vList: string[], map: Map<string, number>) {
    this.vertexList = vList;
    this.initVertexMap = map;

    this.vertexMap = new Map(this.initVertexMap);
  }

  twoVertexLen(oneVertex: string, otherVertex: string) {
    let vLen = this.vertexMap.get(oneVertex + "-" + otherVertex);
    vLen = vLen ? vLen : this.vertexMap.get(otherVertex + "-" + oneVertex);
    return vLen ? vLen : this.MAX_LEN;
  }

  findPath(v: string): { [vertexId: string]: string } {
    const vertexNum = this.vertexList.length;
    // 标级已遍历过的顶点
    this.flagVertex = {};
    this.flagVertex[0] = true;
    this.preVertex = {};
    this.vertexMap = new Map(this.initVertexMap);

    for (let index = 0; index < vertexNum; index++) {
      let minLen = this.MAX_LEN;
      let minVertexId: string | undefined;
      for (let i = 0; i < vertexNum; i++) {
        const vertexId = this.vertexList[i];
        if (!this.flagVertex[vertexId]) {
          const twoVerLen = this.twoVertexLen(v, vertexId);
          if (twoVerLen < minLen) {
            minVertexId = vertexId;
            minLen = twoVerLen;
          }
        }
      }

      if (minVertexId) {
        // 更新邻近节点到起点的距离
        this.flagVertex[minVertexId] = true;
        for (let i = 0; i < vertexNum; i++) {
          const nearVertexId = this.vertexList[i];
          if (!this.flagVertex[nearVertexId]) {
            const nTwoVerLen = this.twoVertexLen(minVertexId, nearVertexId);
            const nStartVerLen = this.twoVertexLen(v, nearVertexId);
            if (nTwoVerLen + minLen < nStartVerLen) {
              this.vertexMap.set(v + "-" + nearVertexId, nTwoVerLen + minLen);
              this.preVertex[nearVertexId] = minVertexId;
            }
          }
        }
      }
    }

    return this.preVertex;
  }
}
